package datastruct.树.线段树;

import javafx.util.Pair;
import test.Leetcode1649;

import java.util.Comparator;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * @author xushenbao
 * @desc 添加描述
 * @create 2020/11/10
 */
public abstract class AbstractNode<V> {

    //region private
    public List<Pair<Integer,V>> originIndexValueList;
    //endregion

    //region protect
    protected int l;
    protected int r;
    public V value;
    protected AbstractNode<V> lson;
    protected AbstractNode<V> rson;

    //region 构造相关
    protected abstract AbstractNode<V> supplier();
    // 子节点完成构造或者更新过，父节点的更新操作,此时父节点的左右儿子已经赋值过
    protected abstract AbstractNode<V> updateNotLeaf();
    protected abstract <T extends AbstractNode> T self();
    // 提供一个非叶子节点，
    protected AbstractNode<V> supplierNotLeaf(int l,int r) {
        AbstractNode<V> supplier = supplier();
        supplier.l=l;
        supplier.r=r;
        return supplier;
    }
    protected AbstractNode<V> supplierLeaf(int pos,V v) {
        AbstractNode<V> supplier = supplier();
        supplier.l = pos;
        supplier.r = pos+1;
        supplier.value = v;
        return supplier;
    }
    //endregion

    private <N extends AbstractNode,I,O> O _visit(N now, Visitable<N,I,O> visitor, I input, int left, int right) {
        // 完全在区间内
        if (now.l >= left && now.r <= right) {
            return visitor.inRange(now,input);
        }
        // 不在区间内，提供一个可合并的空值
        if(now.l>=right||left>=now.r) {
            return visitor.notInRange(now,input);
        }

        return visitor.merge(now,
                _visit((N) now.lson, visitor,input,left,right),
                _visit((N) now.rson, visitor,input,left,right));
    }

    protected <N extends AbstractNode> N build(int l,int r) {
        if(r-l==1) {
            return (N) supplierLeaf(l,originIndexValueList.get(l).getValue());
        } else {
            int mid = (l+r)>>1;
            AbstractNode<V> vAbstractNode = supplierNotLeaf(l, r);
            vAbstractNode.lson = build(l,mid);
            vAbstractNode.rson = build(mid,r);
            return (N) vAbstractNode.updateNotLeaf();
        }
    }

    protected <T> void reBuild(AbstractNode<T> node, T t) {
        if(node.lson==null) {
            node.value = t;
        } else {
            reBuild(node.lson,t);
            reBuild(node.rson,t);
            node.updateNotLeaf();
        }
    }

    protected interface Visitable<N extends AbstractNode,I,O> {
        O inRange(N node,I input);
        O notInRange(N node,I input);
        O merge(N node,O leftOutput,O rightOutput);
    }
    //endregion


    //region static
    static <T> int lower_search(int left, int right, T aim, Function<Integer, T> indexToObject, Comparator<T> comparator) {
        while (left < right) {
            int mid = (left + right) >> 1;
            if (comparator.compare(indexToObject.apply(mid), aim) < 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    static <T> int upper_search(int left, int right, T aim, Function<Integer, T> indexToObject, Comparator<T> comparator) {
        while (left < right) {
            int mid = (left + right) >> 1;
            if (comparator.compare(indexToObject.apply(mid), aim) <= 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    static <A,B> List<Pair<A,B>> zip(List<A> aList,List<B> bList ) {
        if(aList.size()!=bList.size()) {
            throw new RuntimeException(String.format("两个列表的大小必须相等,aList size:%s,bList size:%s", aList,bList));
        }
        return IntStream.range(0,aList.size()).mapToObj(i->new Pair<>(aList.get(i),bList.get(i))).collect(Collectors.toList());
    }
    //endregion

    //region public
    public <N extends AbstractNode> N treeBuild(List<Integer> indexList,List<V> valueList){
        return treeBuild(zip(indexList,valueList));
    }
    public <N extends AbstractNode> N treeBuild(List<Pair<Integer, V>> indexValue){
        // 1. 将传入的数据按索引排序

        originIndexValueList = indexValue.stream().sorted(Comparator.comparing(Pair::getKey)).collect(Collectors.toList());
        // 2. 构建树
        AbstractNode build = build(0, indexValue.size());
        build.originIndexValueList = originIndexValueList;
        return (N) build;
    }
    public <N extends AbstractNode,I,O> O visit(Visitable<N,I,O> visitor, I input, int left, int right) {
        int l = lower_search(0,originIndexValueList.size(),left,i->originIndexValueList.get(i).getKey(),Integer::compare);
        int r = upper_search(0,originIndexValueList.size(),right,i->originIndexValueList.get(i).getKey(),Integer::compare);
        if(l>=r) {
//            return visitor.notInRange(self(),input);
            return visitor.notInRange(self(),input);
        }
        return _visit(self(), visitor,input,l,r);
    }

    public <O> O query(Visitable<? extends AbstractNode,Void,O> visitor, int left, int right) {
        return visit(visitor,null,left,right);
    }

    public <I> void operate(Visitable<? extends AbstractNode,I,Void> visitor, I input, int left, int right) {
        visit(visitor,input,left,right);
    }

    //endregion
}

